#include <iostream>
#include <vector>

using namespace std;

class Solution1
{
  private:
    vector<int> memo;
    int tryRob(vector<int> &nums, int index)
    {
        if (index >= nums.size())
            return 0;
        if (memo[index] != -1)
            return memo[index];
        int res = 0;
        for (int i = index; i < nums.size(); i++)
            res = max(res, nums[i] + tryRob(nums, i + 2));
        memo[index] = res;
        return res;
    }

  public:
    int rob(vector<int> &nums)
    {
        memo = vector<int>(nums.size(), -1);
        return tryRob(nums, 0);
    }
};
// 100.00 %
class Solution
{
  public:
    vector<int> memo;
    int rob(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 0)
            return 0;
        vector<int> memo;
        memo = vector<int>(n, -1);
        memo[0] = nums[0];
        if (n == 1)
            return memo[0];
        memo[1] = max(nums[1], memo[0]);
        if (n == 2)
            return memo[1];
        for (int i = 2; i < n; i++)
            memo[i] = max(nums[i] + memo[i - 2], memo[i - 1]);
        return memo[n - 1];
    }
};

int main()
{
    int arr[] = {2, 7, 9, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    vector<int> num(arr, arr + n);
    cout << Solution().rob(num);
    return 0;
}